package com.lfg.leetcode.leetcode0;

public class No91numDecodings {

    public static void main(String[] args) {
        int ret = numDecodings("2101");
        System.out.println("[" + ret + "]");
    }

    public static int numDecodings(String s) {
        if(s.charAt(0) == '0'){
            return 0;
        }
        int length = s.length();
        int[] dp = new int[length+1];
        dp[0] = 1;

        for (int i = 1; i <= length; i++) {
            if (s.charAt(i-1) != '0') {
                dp[i] = dp[i - 1];
            }
            if(i> 1 && s.charAt(i-2) != '0' &&  ((s.charAt(i-2) -'0') * 10 + s.charAt(i-1) -'0') <= 26 ){
                dp[i] += dp[i - 2];
            }
        }
        return dp[dp.length-1];
    }

    public static int numDecodings12(String s) {
        if (null == s) {
            return 0;
        }
        int length = s.length();
        if (length <= 0) {
            return length;
        }
        int[] dp = new int[length];
        if (s.charAt(0) == '0') {
            return 0;
        }
        dp[0] = 1;
        if (length == 1) {
            return 1;
        }
        char c1 = s.charAt(0);
        char c2 = s.charAt(1);

        if (c2 == '0') {
            if ((c1 == '1' || c1 == '2')) {
                dp[1] = 1;
            } else {
                return 0;
            }
        } else if (c2 > '6') {
            if (c1 == '1') {
                dp[1] = 2;
            } else {
                dp[1] = 1;
            }
        } else if (c1 == '2' || c1 == '1') {
            dp[1] = 2;
        } else {
            dp[1] = 1;
        }
        for (int i = 2; i < length; i++) {
            c1 = s.charAt(i - 1);
            c2 = s.charAt(i);
            if (c2 == '0') {
                if ((c1 == '1' || c1 == '2')) {
                    dp[i] = dp[i - 2];
                } else {
                    return 0;
                }
            } else if (c2 > '6') {
                if (c1 == '1') {
                    dp[i] = dp[i - 1] + dp[i - 2];
                } else {
                    dp[i] = dp[i - 1];
                }
            } else if (c1 == '2' || c1 == '1') {
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[length - 1];
    }

    public static int numDecodings2(String s) {
        if (null == s) {
            return 0;
        }
        if (s.length() <= 0) {
            return s.length();
        }
        return numDecodings(s, 0, s.length());
    }

    public static int numDecodings(String s, int index, int length) {
        int ret = 0;
        if (index >= length) {
            return 1;
        }
        char c = s.charAt(index);
        if (c >= '1' && c <= '9') {
            ret += numDecodings(s, index + 1, length);
        } else {
            return 0;
        }
        if (c == '1' && index + 1 < length) {
            return ret + numDecodings(s, index + 2, length);
        }
        if (c == '2' && index + 1 < length && s.charAt(index + 1) <= '6') {
            return ret + numDecodings(s, index + 2, length);
        }
        return ret;
    }
}

